package com.str.graphs;

import com.str.PQ.PriorityQueue;

public class Dijkstra2 {

  private static class ElemV implements Comparable {
  	int vertex;
  	int distance;
  	
  	ElemV(int v, int d) {
  	  vertex = v;
  	  distance = d;
    }
    
    public int compareTo(Object that) {
      ElemV other = (ElemV) that;
      return distance - other.distance;
    }
  }

  private static void printout(Graph g, int s, int[] d) {
    for (int i=0; i<g.n(); i++)
      System.out.println(s + " -> " + i + " (" + d[i] + ")");
  }
  
// Dijkstra's shortest paths algorithm w/ priority queue
  public static void dijkstra(Graph g, int s, PriorityQueue heap) {
    boolean[] visited = new boolean[g.n()];
    int[] d = new int[g.n()];        // Distance array
    for (int i=0; i < g.n(); i++) {     // Initialize
      visited[i] = false;
      d[i] = Integer.MAX_VALUE;
    }
    d[s] = 0;
    ElemV temp = new ElemV(s, d[s]);     // Initialize heap array 
    heap.add(temp);     
    
    for (int i=0; i < g.n(); i++) {     // Now, get distances
      int v;
      do {
        if (heap.isEmpty()) return; // Nothing to remove
        temp = (ElemV) heap.removeMin();
        v = temp.vertex;
      } while (visited[v]);
      visited[v] = true;      
      if (d[v] == Integer.MAX_VALUE) return; // Rest of vertices unreachable
      for (int w = g.first(v); w < g.n(); w = g.next(v,w))
        if (d[w] > (d[v] + g.weight(v,w))) { // Update D
	      d[w] = d[v] + g.weight(v,w);
	      temp = new ElemV(w, d[w]);
	      heap.add(temp);    // Insert new distance in heap
        }
    }
    printout(g, s, d);
  }
}
